public class SameTree {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) {
            // 两树为空, 相同
            return true;
        }

        // 经过上面判断后, 一定有一棵树不为空

        if(p == null || q == null || q.val != p.val) {
            // 有一棵树不为空, 或者树节点不相同, 两棵树不相同
            return false;
        }

        // 左子树是否相同
        boolean left = isSameTree(p.left, q.left);
        boolean right = isSameTree(p.right, q.right);
        return left && right;
    }
}
